Hg
Name: Class 12 STICK TO YOUR WALL IN STUDY AREA
___________________________________________________________________________________________________________________________________
___________________________________________________________________________________________________________________________________
The Hg Classes (8
th
to 12
th
) By: Er Hershit Goyal (B.Tech. IIT BHU), 134-SF, Woodstock Floors, Nirvana Country, Sector 50, GURUGRAM +91 9599697178.
fb.me/thehgclasses linkedin.com/company/the-hg-classes instagram.com/the_hg_classes g.page/the-hg-classes-gurugram thehgclasses.co.in
LINEAR PROGRAMMING
Definitions:
• Linear Programming Problem (or LPP): A linear programming problem is one that is concerned with
finding the optimal value (max or min) of a linear function of several variables, subject to given
constraints.
• Decision Variables: the variables (x, y etc) associated with the given problem.
• Objective Function: the linear function to be optimized is called an objective function. It is generally
denoted by Z = ax + by, where x and y are the decision variables and a and b are arbitrary constants.
• Non-negative constraints: the conditions that the variables are non-negative i.e., x ≥ 0; y ≥ 0
• Linear constraints: the other conditions given in the problem represented as linear inequalities.
• Feasible Region (or solution region): the common region satisfying all the constraints.
• Feasible solutions: points lying in the feasible region.
• Infeasible solution: any point outside the feasible region.
• Optimal solution: any point in the feasible region, that gives the optimum (max or min) value of the
objective function.
• Corner Point: Point of intersection of two boundary lines
Corner Point method (for finding the optimal solution):
i) Find the feasible region of the given LPP and determine its corner points.
ii) Evaluate the objective function Z = ax + by at each corner point. Let M and m be the respective
largest and smallest values at these points.
iii) If the feasible region is BOUNDED, then M and m respectively the maximum and minimum
values of Z.
If the feasible region is UNBOUNDED, then
i) M is maximum value of Z, if the region satisfying ax + by > M has no point common with
the feasible region, otherwise Z has no maximum value.
ii) m is the minimum value of Z, if the region satisfying ax + by < m has no point common
with the feasible region, otherwise Z has no minimum value.
• If two corner points (say A and B) of a feasible region are both optimal solutions of same type, then all
the points on the line segment AB are optimal solutions of that same type.
• Linear Programming can be applied to following category of problems:
o Diet Problems
o Manufacturing problems
o Transportation problems
